//
//  78. 子集.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/22.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution78 {
    // 子集，采用回溯法时，子集实际上是树的所有节点
    var result: [[Int]] = [[]]
    var path: [Int] = []
    func subsets(_ nums: [Int]) -> [[Int]] {
        backTrace(nums, start: 0)
        return result
    }
    func backTrace(_ nums: [Int], start: Int) {
        for i in start..<nums.count {
            path.append(nums[i])
            result.append(path)
            backTrace(nums, start: i + 1)
            path.removeLast()
        }
    }
    // 第二种解法
    //    func subsets(_ nums: [Int]) -> [[Int]] {
    //        var result: [[Int]] = []
    //        for i in 0..<nums.count {
    //            let newResult = createNew(nums, result: &result, i)
    //            result.append(contentsOf: newResult)
    //        }
    //        result.insert([], at: 0)
    //        return result
    //    }
    //    func createNew(_ numss: [Int], result: inout [[Int]],_ index: Int) -> [[Int]] {
    //        var newArray:[[Int]] = []
    //        newArray.append([numss[index]])
    //        // 在原有数组基础上添加新的元素
    //        for i in 0..<result.count {
    //            var item = result[i]
    //            item.append(numss[index])
    //            newArray.append(item)
    //        }
    //        return newArray
    //    }
    //
    static func test(){
        let solution = Solution78()
        let nums = [1,2,3]
        let result = solution.subsets(nums)
        print(result)
    }
}
